package com.zdp.leetcodeMiddle;

import java.util.Arrays;

public class 把箱子放进仓库里1 {
    /*
    * 题目描述： （具体的还是去官网上看图把）
    * 给定两个正整数数组 boxes 和 warehouse ，分别包含单位宽度的箱子的高度，以及仓库中 n 个房间各自的高度。
    * 仓库的房间分别从 0 到 n - 1 自左向右编号， warehouse[i] （索引从 0 开始）是第 i 个房间的高度。
    箱子放进仓库时遵循下列规则：
    箱子不可叠放。
    你可以重新调整箱子的顺序。
    箱子只能从左向右推进仓库中。
    如果仓库中某房间的高度小于某箱子的高度，则这个箱子和之后的箱子都会停在这个房间的前面。
    你最多可以在仓库中放进多少个箱子？
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/put-boxes-into-the-warehouse-i
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    * */
    /*
    * 贪心算法：每次只要算出我当前位置可以放进来的高度就可以了
    * 只关注当前位置（局部）
    * */
    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
        //首先对仓库进行重塑，仓库中当前位置可以放进的最高的箱子是 之前箱子的最低高度，超过这个高度会被卡住
        //当然也有可能当前位置的高度更低，所以重塑这个仓库数组，数组中每个位置的高度都是该位置可以放入的最高高度的箱子
        int minHigh = warehouse[0];
        for(int i=1;i<warehouse.length;i++){
            if(minHigh>warehouse[i])
                minHigh = warehouse[i];
            else if(warehouse[i]>minHigh)
                warehouse[i] = minHigh;
        }
        //对箱子进行排序，小的先进去，才可以放更多
        Arrays.sort(boxes);
        int count=0;
        //开始将箱子推入,箱子按从小到大排序，如果小的推不进去，所以如果当前位置箱子推不进去，换箱子是没有意义的
        //换位置才是有意义的。
        //遍历仓库的位置
        int j=0;
        for(int i=warehouse.length-1;i>=0&&j<boxes.length;i--){
            if(boxes[j]<=warehouse[i]){
                count++;
                j++;
            }
        }
        return count;
    }
}
